【题解】 [SDOI2016]生成魔咒 后缀自动机.SAM bzoj4516/luogu4070 | Qiuly's blog!

【题解】 [SDOI2016]生成魔咒 后缀自动机.SAM bzoj4516/luogu4070

Posted on | Edited on | In | Comments:

一眼题目。

题目简述如下：

  • 任务一：支持询问当前本质不同的子串的个数
  • 任务二：支持插入

很显然后缀自动机可以解决胜任，正好今天刚学了后缀自动机，那么就将它定为练手题了。

插入是很简单的，至于询问本质不同的字串的个数，我们知道新插入一个节点 $now$ 对答案的贡献是: $ |max(now)| - |min(now)| + 1$ 。我们建后缀自动机的时候只保存了 $max(now)$ ，难道还要保存一个 $min(now)$ 吗？其实不需要，根据其性质可以得到：$|max(now)| - |max(fa[now])|$，直接计算即可。

注意数据范围较大，记得开 $longlong​$ ！

*注：文中的 $|S|​$ 指的是字符串 $S​$ 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=2e5+2;
const int inf=1e9+9;

template<typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

struct SAM{
    ll ans;
    std::map<int,int> ch[N];
    int last,cnt,len[N],fa[N];
    inline void Insert(int c){
        int p=last,now=last=++cnt;
        len[now]=len[p]+1;
        while(p&&!ch[p][c])ch[p][c]=now,p=fa[p];
        if(!p)fa[now]=1;
        else{
            int q=ch[p][c];
            if(len[q]==len[p]+1)fa[now]=q;
            else{
                int copy=++cnt;
                len[copy]=len[p]+1,ch[copy]=ch[q];
                fa[copy]=fa[q],fa[q]=fa[now]=copy;
                while(p&&ch[p][c]==q)ch[p][c]=copy,p=fa[p];
            } 
        }
        ans+=len[now]-len[fa[now]];
        return;
    }
}sam;

int main(){
    int n;IN(n);
    sam.last=sam.cnt=1;
    for(int i=1;i<=n;++i){
        int c;IN(c);
        sam.Insert(c);
        printf("%lld\n",sam.ans);
    }
    return 0;
}

本文标题:【题解】 [SDOI2016]生成魔咒 后缀自动机.SAM bzoj4516/luogu4070

文章作者:Qiuly

发布时间:2019年02月14日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/02/14/[题解]luoguP4070/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。